🎯 반지름 r1 ~ r2 사이의 정수 좌표 개수 구하기

2차원 평면에서 원점(0,0)을 기준으로
두 원 사이에 존재하는 정수 좌표의 개수를 구하는 문제입니다.

이 문제는 단순 기하 문제가 아니라
👉 격자 좌표 + 포함-배제 + 대칭성 활용 문제입니다.

1️⃣ 핵심 개념

🔹 원 내부 판별 조건

원점에서 (x, y)까지의 거리:

$$\sqrt{x^2 + y^2}$$

원이 반지름 r일 때 내부 조건은:

$${x^2 + y^2}\le{r^2}$$

✔️ 피타고라스 정리 기반
✔️ "거리 조건" 문제

🔹 문제의 구조

구해야 하는 것:

$${r1}\le\sqrt{x^2 + y^2}\le{r2}$$

제곱 형태로 바꾸면:

$${r1^2}\le{x^2 + y^2}\le{r2^2}$$

2️⃣ 핵심 아이디어

직접 두 조건을 동시에 세면 복잡해지므로, 이렇게 생각합니다.

큰 원 내부 개수 - 작은 원 내부 개수

단,
작은 원은 경계를 제외해야 하므로:

$${(x^2 + y^2}\le{r2^2)-}{(x^2 + y^2}\le{r1^2 - 1)}$$

3️⃣ 구현 코드

function solution(r1, r2) {

    function count(rr) {
        let sum = 0;
        let maxX = Math.floor(Math.sqrt(rr));

        for (let x = 0; x <= maxX; x++) {
            let y = Math.floor(Math.sqrt(rr - x*x));
            let line = y * 2 + 1;   // y축 대칭

            if (x > 0) line *= 2;   // x축 대칭

            sum += line;
        }

        return sum;
    }

    return count(r2*r2) - count(r1*r1 - 1);
}

(r1*r1 - 1)을 하는 이유

작은 원의 경계까지 포함하면

$${x^2 + y^2=r1^2}$$

인 점도 같이 빠져버리게 됩니다.
r1 이상을 포함해야 하므로 작은 원은 "엄밀히 내부"만 제거해야 합니다.

✍️ 한 줄 정리

기하 조건을 제곱 형태로 변환하고, 포함-배제 + 대칭성을 이용해 O(r)으로 정수 격자점을 계산하는 문제